package com.dq.utils;

public class LIS {
    public static int Lis(int[] array){

        int[] piece = new int[array.length];
        piece[0] = array[0];
        int len=1;
        for (int i = 1; i < array.length; i++) {
            if(piece[len-1]<array[i]) piece[len++] = array[i];
            else{
                int index = binarySearch(piece, len, array[i]);
                piece[index] = array[i];
            }
        }
        return len;
    }
    //[0,len]
    public static int binarySearch(int[] array,int len, int target){
        int left = 0, right = len-1;

        while(left<=right){
            int mid = left + (right-left)/2;

            if(array[mid]>target){
                right = mid-1;
            }else if(array[mid]==target){
                right = mid -1 ;
            }else if(array[mid]<target){
                left = mid+1;
            }
        }

        return left;

    }

    public static void main(String[] args) {
        int[] a = {4,2 ,3 ,1, 5};
        System.out.println(Lis(a));
    }
}
